package main.Q1_100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Q91_100 {
    public static void main(String[] args) {
        System.out.println("Question91：解码方法");
        System.out.println("Question92：反转链表 II");
        System.out.println("Question93：复原 IP 地址");
        System.out.println("Question94：二叉树的中序遍历");
        System.out.println("Question95：不同的二叉搜索树 II");
        System.out.println("Question96：不同的二叉搜索树");
        System.out.println("Question97：交错字符串");
        System.out.println("Question98：验证二叉搜索树");
        System.out.println("Question99：恢复二叉搜索树");
        System.out.println("Question100：相同的树");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question91 {
    public int process(char[] str, int index) {
        if (index >= str.length) return 1;
        int oneChar = 0, twoChar = 0;
        if (str[index] != '0') {
            oneChar = process(str, index + 1);
        }
        if ((str[index] - 64) * 10 + str[index + 1] - 64 < 27) {
            twoChar = process(str, index + 2);
        }
        return oneChar + twoChar;
    }

    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 10];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) != '0') f[i] = f[i - 1]; //单独解码s[i - 1]
            if (i >= 2) {
                int t = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
                if (t >= 10 && t <= 26) f[i] += f[i - 2]; //将s[i - 2] 和 s[i - 1]组合解码
            }
        }
        return f[n];
    }
}

class Question92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode vir = new ListNode(0);
        vir.next = head;
        ListNode pre = vir;
        for(int i = 1; i < left; i++){
            pre = pre.next;
        }
        head = pre.next;
        for(int i = left; i < right; i++){
            ListNode nex = head.next;
            head.next = nex.next;
            nex.next = pre.next;
            pre.next = nex;
        }
        return vir.next;
    }
}

class Question93 {
    int n;
    List<String> ans = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        this.n = s.length();
        process(0, s, new ArrayList<String>());
        return ans;
    }

    public void process(int start, String s, ArrayList<String> list) {
        int len = list.size();
        if (len > 4) return;
        if (start == n && len == 4) {
            // 拼接list中的所有字符串
            String temp = "";
            for (String str : list) {
                temp += str + ".";
            }
            ans.add(temp.substring(0, temp.length() - 1));
            return;
        }
        for (int i = start; i < n; i++) {
            String temp = s.substring(start, i + 1);
            int num = Integer.parseInt(temp);
            if (num > 255) return;
            if (num == 0 && temp.length() == 1) {  // 遏制前导零
                list.add(temp);
                process(i + 1, s, list);
                list.remove(list.size() - 1);
            } else {
                if (num <= 255 && temp.charAt(0) != '0') {
                    list.add(temp);
                    process(i + 1, s, list);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}

class Question94 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

class Question95 {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return process(1, n);
    }

    public List<TreeNode> process(int start, int end) {
        List<TreeNode> result = new LinkedList<TreeNode>();
        if (start > end) {
            result.add(null);
            return result;
        }
        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            List<TreeNode> leftTrees = process(start, i - 1);
            // 获得所有可行的右子树集合
            List<TreeNode> rightTrees = process(i + 1, end);
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    result.add(currTree);
                }
            }
        }
        return result;
    }
}

class Question96 {
    public int numTrees(int n) {
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }
}

class Question97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1 = s1.length(), length2 = s2.length(), length3 = s3.length();
        if (length1 + length2 != length3) return false;
        char[] str1 = s1.toCharArray(), str2 = s2.toCharArray(), str3 = s3.toCharArray();
        boolean[][] dp = new boolean[length1 + 1][length2 + 1];
        dp[0][0] = true;
        for (int i = 0; i <= length1; i++) {
            for (int j = 0; j <= length2; j++) {
                int temp = i + j - 1;
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i - 1][j] && str1[i - 1] == str3[temp]);
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j - 1] && str2[j - 1] == str3[temp]);
                }
            }
        }
        return dp[length1][length2];
    }
}

class Question98 {
    public class Info {
        public boolean isSearch;
        public Long max;//左子树最大值
        public Long min;//右子树最小值

        public Info(boolean isSearch, Long max, Long min) {
            this.isSearch = isSearch;
            this.max = max;
            this.min = min;
        }
    }

    public Info process(TreeNode root) {
        if (root == null) return new Info(true, Long.MIN_VALUE, Long.MAX_VALUE);
        Info left = process(root.left);
        Info right = process(root.right);
        boolean isSearch = false;
        Long max = Math.max(root.val, right.max);
        Long min = Math.min(root.val, left.min);
        if (left.isSearch && right.isSearch && root.val > left.max && root.val < right.min) {
            isSearch = true;
            return new Info(isSearch, max, min);
        } else return new Info(isSearch, max, min);
    }

    public boolean isValidBST(TreeNode root) {
        return process(root).isSearch;
    }
}

class Question99 {
    public void recoverTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode x = null, y = null, pred = null;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pred != null && root.val < pred.val) {
                y = root;
                if (x == null) {
                    x = pred;
                } else {
                    break;
                }
            }
            pred = root;
            root = root.right;
        }
        swap(x, y);
    }

    public void swap(TreeNode x, TreeNode y) {
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }
}

class Question100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}